class Solution {
public:
    struct compare
    {
        bool operator()(const int& a, const int& b)
        {
            return a > b;
        }

    };
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, compare> heap;
        int sum = 0;
        int sum_correct = 0;
        int mini = INT_MAX / 2;
        for (int i = 0;i < nums.size();i++)
        {
            int tmp = nums[i] > 0 ? nums[i] : -nums[i];
            mini = min(mini, tmp);
            sum_correct += tmp;
            sum += nums[i];
            if (nums[i] < 0)
            {
                heap.push(nums[i]);
            }
        }
        int turns = 0;
        if (heap.size() >= k)
        {
            for (int i = 0;i < k;i++)
            {
                turns += -heap.top();
                heap.pop();
            }
            return sum + turns * 2;
        }
        else
        {
            if ((k - heap.size()) % 2 == 0)
            {
                return sum_correct;
            }
            else
            {
                return sum_correct - 2 * mini;



            }

        }

    }
};